// https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
// 17. 电话号码的字母组合
// 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
// 给出数字到字母的映射（与电话按键相同）。注意 1 不对应任何字母
// 使用回溯法

function letterCombinations(digits: string): string[] {
    const result: string[] = [];
    const list: string[] = [];

    if (!digits || digits.length < 1) return result;

    const map = new Map([
        ['2', 'abc'],
        ['3', 'def'],
        ['4', 'ghi'],
        ['5', 'jkl'],
        ['6', 'mno'],
        ['7', 'pqrs'],
        ['8', 'tuv'],
        ['9', 'wxyz'],
    ]);

    helper(digits, 0);

    function helper(digits: string, n: number) {
        if (list.length >= digits.length) {
            result.push(list.join(''));
            return;
        }

        const digit = digits[n];
        const letters = map.get(digit);
        if (letters === undefined) return;

        for (let i = 0; i < letters.length; i++) {
            list.push(letters[i]);
            helper(digits, n + 1);
            list.pop();
        }
    }

    return result;
}
